#include <iostream>
#include <string>

using namespace std;

//验证回文串
class Solution {
public:
    bool IsLetterOrNumber (char ch)
    {
        return (ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')||(ch>='0'&&ch<='9');
    }

    bool isPalindrome(string s) {
    for(auto& ch:s)
    {
        if(ch>='a'&&ch<='z')
            ch-=32;
    }
    int begin=0;
    int end=s.size()-1;
    while(begin<end)
    {
        while(begin<end&&!IsLetterOrNumber(s[begin]))
            begin++;
        while(begin<end&&!IsLetterOrNumber(s[end]))
            end--;
        if(s[begin]!=s[end])
        {
           return false;
        }
        else
        {
            begin++;
            end--;
        }    
    }
    return true; 
    }
};


//字符串相加
class Solution {
public:
    string addStrings(string num1, string num2) {
      int end1=num1.size()-1;
      int end2=num2.size()-1;
      string retstr;
      int next=0;
      while(end1>=0||end2>=0)
      {
        int val1=0;
        int val2=0;
        if(end1>=0)
            val1=num1[end1]-'0';
        if(end2>=0)
            val2=num2[end2]-'0';
        int ret = val1+val2+next;
        if(ret>9)
        {
            next=1;
            ret-=10;
        }
        else
        {
            next=0;
        }
        retstr+=(ret+'0');
        end1--;
        end2--;
      }
      if(next==1)
        retstr+='1';
    reverse(retstr.begin(),retstr.end());
    return retstr;
    }  
};

//字符串相乘
class Solution {
public:
string addStrings(string& num1, string& num2) {
       int end1=num1.size()-1;
       int end2=num2.size()-1;
       string retstr;
       int next=0;
       while(end1>=0||end2>=0)
       {
            int val1=0;
            int val2=0;
            int tmp=0;
            if(end1>=0)
                val1=num1[end1]-'0';
            if(end2>=0)
                val2=num2[end2]-'0';
            int ret=val1+val2+next;
            if(ret>9)
            {
                next=1;
                ret-=10;
            }
            else
            {
                next=0;
            }
            retstr+=(ret+'0');
            end1--;
            end2--;
       }
       if(next==1)
            retstr+='1';
        reverse(retstr.begin(),retstr.end());
       return retstr;
    }  
    
    string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0")
            return "0";
        int end1=num1.size()-1;
        string retstr;
        string zero;
        while(end1>=0)
        {
            string tmp;
            int val1=num1[end1]-'0';
            for(int i=0;i<val1;i++)
            {
                tmp=addStrings(tmp,num2);
            }
            tmp+=zero;
            zero+='0';
            retstr=addStrings(retstr,tmp);
            end1--;
        }
        return retstr;
    }
};


//反转字符串2
class Solution {
public:
    string Swap(string& s,int begin ,int end)
    {
        while(begin<end)
        {
            swap(s[begin],s[end]);
            begin++;
            end--;
        }
        return s;
    }
    string reverseStr(string s, int k) {
      int n=s.size();
      for(int i=0;i<n;i+=2*k)
      {
        int end=i+k-1;
        if(end>=n)
            end=n-1;
        Swap(s,i,end);
      }
      return s;
    }
};

//反转字符串里面的单词
class Solution {
public:
    string& Swap(string& s,int begin,int end)
    {
        while(begin<end)
        {
            swap(s[begin],s[end]);
            begin++;
            end--;
        }
        return s;
    }
      string reverseWords(string s) {
       int begin =0;
       int end=0;
       for(int i=0;i<s.size();i++)
       {
            if(s[i] ==' ')
            {
                Swap(s,begin,end-1);
                begin=end+1;
                end++;
            }
            else
            {
                end++;
            }
       }
       if(begin<s.size())
       {
        Swap(s,begin,s.size()-1);
       }
       return s;
    }
};